#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

/**
 * @brief ElemType 保存的二叉树的数据类型
 */
typedef char ElemType;

/**
 *二叉树节点数据类型
 */
typedef struct BinaryTreeNode{
    ElemType data;
    struct BinaryTreeNode *leftChild,*rightChild;
}BinaryTreeNode,*BinaryTreeLink;

typedef struct BinaryTreeStackNode{
    BinaryTreeNode * data;
    struct BinaryTreeStackNode * next;
}BinaryTreeStackNode,*BinaryTreeStack;

/**
 *队列节点的数据类型
 */
typedef struct BinaryTreeQueueNode{
    BinaryTreeNode * data;
    struct BinaryTreeQueueNode * next;
}BinaryTreeQueueNode;

/**
 *队列的数据类型
 */

typedef struct BinaryTreeQueue{
    BinaryTreeQueueNode* front; //允许删除的一端
    BinaryTreeQueueNode* rear; //允许插入的一端
}BinaryTreeQueue;

typedef struct
{
    int weight;
    int parent;
    int leftChild;
    int rightChild;
}HuffmanNode, *HuffmanTree;
typedef char **HuffmanCode;


/**
 * @brief QueueInit
 *      使front rear指向一个地址 front（队首）无指向
 * @param queue
 */
void QueueInit(BinaryTreeQueue *queue)
{
    queue->front = queue->rear = (BinaryTreeQueueNode*)malloc(sizeof(BinaryTreeQueueNode));
    queue->front->next = NULL;
}

void QueueEnData(BinaryTreeQueue *queue, BinaryTreeNode * data)
{
    BinaryTreeQueueNode * node = (BinaryTreeQueueNode*)malloc(sizeof(BinaryTreeQueueNode));
    node->data = data;
    node->next = NULL; /*记得将队尾置空*/
    queue->rear->next = node;
    queue->rear = node;
}

int QueueIsEmpty(const BinaryTreeQueue *queue)
{
    if(queue->front == queue->rear){
        return 1;
    }else{
        return -1;
    }
}

void QueueDe3(BinaryTreeQueue *queue,BinaryTreeNode * node)
{
    /*判断queue是否为空*/
    if(QueueIsEmpty(queue) > 0){
        node = NULL;
    }else{
        BinaryTreeQueueNode * node1 = queue->front->next;
        *node = *(node1->data);
        queue->front->next = node1->next;
        /*处理删除的是队列中的最后一个节点*/
        if(queue->rear == node1)
            queue->rear = queue->front;
        free(node1);
    }

}

void QueueTraverse(BinaryTreeQueue *que)
{
    printf("LinkQueueTraverse:\n");
    /* 这种遍历修改了que指针
    BinaryTreeQueue *queue = que;
    while(queue->front->next != NULL){
        queue->front = queue->front->next;
        printf("%c\n",queue->front->data.data);
    }
    */
    BinaryTreeQueue queue = *que;
    while(queue.front->next != NULL){
        queue.front = queue.front->next;
        printf("%c\n",queue.front->data->data);
    }
}

/**
 * @brief CreateBinaryTree 输入字符先序创建二叉树
 * @return 生成的二叉树
 */
BinaryTreeLink CreateBinaryTree(){
    ElemType input;
    BinaryTreeLink tree;
    scanf("%c",&input);
    if(input=='#')tree=NULL;
    else{
        tree = (BinaryTreeLink)malloc(sizeof(BinaryTreeNode));
        tree->data = input;
        tree->leftChild = CreateBinaryTree();
        tree->rightChild = CreateBinaryTree();
    }
    return tree;
}
void CreateBinaryTree2(BinaryTreeLink tree,ElemType *arr){
    ElemType input;
    sscanf(arr,"%c",&input);
    arr++;
    if(input=='#')tree=NULL;
    else{
        tree = (BinaryTreeLink)malloc(sizeof(BinaryTreeNode));
        tree->leftChild = (BinaryTreeLink)malloc(sizeof(BinaryTreeNode));
        tree->rightChild = (BinaryTreeLink)malloc(sizeof(BinaryTreeNode));
        tree->data = input;

//        CreateBinaryTree2(tree->leftChild,arr);
//        CreateBinaryTree2(tree->rightChild,arr);
        tree->leftChild->data = '2';
        tree->rightChild->data = '2';
        printf("input=%c\n",input);
    }
}

/**
 * @brief PreOrderTraverse 先序遍历的递归实现
 * @param tree
 */
void PreOrderTraverse(BinaryTreeLink tree){
    if(tree){
       printf("%c\n",tree->data);
       PreOrderTraverse(tree->leftChild);
       PreOrderTraverse(tree->rightChild);
    }
}
/**
 * @brief InOrderTraverse 中序遍历的递归实现
 * @param tree
 */
void InOrderTraverse(BinaryTreeLink tree){
    if(tree){
       InOrderTraverse(tree->leftChild);
       printf("%c\n",tree->data);
       InOrderTraverse(tree->rightChild);
    }
}
/**
 * @brief PostOrderTraverse 后序遍历的递归实现
 * @param tree
 */
void PostOrderTraverse(BinaryTreeLink tree){
    if(tree){
       PostOrderTraverse(tree->leftChild);
       PostOrderTraverse(tree->rightChild);
       printf("%c\n",tree->data);
    }
}

void test_reculsion_traverse()
{
    /*
     * 测试二叉树（先序输入）：IRO##A##CG#W##R##
     */
    BinaryTreeLink tree = CreateBinaryTree();
    printf("PreOrderTraverse:\n");
    PreOrderTraverse(tree);
    printf("InOrderTraverse:\n");
    InOrderTraverse(tree);
    printf("PostOrderTraverse:\n");
    PostOrderTraverse(tree);
}

void test_level_traverse()
{
    BinaryTreeLink tree = CreateBinaryTree();
    BinaryTreeQueue queue;
    QueueInit(&queue);
    QueueEnData(&queue,tree); //根节点入队
    BinaryTreeNode * node = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
    printf("LevelTraverse:\n");
    while(QueueIsEmpty(&queue) < 0){
        QueueDe3(&queue,node); // 队头元素出队
        printf("%c\n",node->data);
        if(node->leftChild != NULL)
            QueueEnData(&queue,node->leftChild);
        if(node->rightChild != NULL)
            QueueEnData(&queue,node->rightChild);
    }
}

BinaryTreeStack StackCreate()
{
    BinaryTreeStack head = (BinaryTreeStack )malloc(sizeof(BinaryTreeStackNode));
    head->data = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
    head->next = NULL;
    return head;
}
void StackPush(BinaryTreeStack stack,BinaryTreeNode data)
{
    BinaryTreeStackNode *node = (BinaryTreeStack )malloc(sizeof(BinaryTreeStackNode));
    node->data= (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
    *(node->data)= data;
    node->next = stack->next;
    stack->next = node;
}

void StackTraverse(BinaryTreeStack stack)
{
    printf("StackTraverse:\n");
    BinaryTreeStack temp = stack;
    while(temp->next != NULL)
    {
        temp = temp->next;
        printf("%c\n",temp->data->data);
    }
}

void StackPop(BinaryTreeStack stack,BinaryTreeNode* data)
{
    BinaryTreeStackNode *node = (BinaryTreeStack )malloc(sizeof(BinaryTreeStackNode));
    node = stack->next;
    stack->next = node->next;

    node->next = NULL;
    *data = *(node->data);
    free(node);
}
void StackPopTestWangDao(BinaryTreeStack stack,BinaryTreeNode *data)
{
    BinaryTreeStackNode *node = (BinaryTreeStack )malloc(sizeof(BinaryTreeStackNode));
    node = stack->next;
    stack->next = node->next;

    node->next = NULL;
    data = node->data;
}
int StackIsEmpty(BinaryTreeStack stack){
    if(stack->next == NULL)
        return 1;
    else
        return -1;
}

void test_wang_dao(BinaryTreeStack stack, BinaryTreeLink tree)
{
    StackPopTestWangDao(stack,tree);
    printf("%c\n",tree->data);
    tree = tree->rightChild;
}

void test_non_recursion_traverse()
{
    BinaryTreeStack stack;
    stack = StackCreate();
    BinaryTreeLink tree = CreateBinaryTree();
    /**
     * @brief data 这个变量有很重要的作用
     * data用来保存tree为空后出栈的数据。
     * 在王道2017考研数据结构114页中出栈仍然
     * 用tree保存出栈数据，这会发生段错误。
     * 原因是因为：只有tree为空才能执行出栈操作，
     * 既然tree已经为空，又怎么能够保存出栈的节点数据呢？
     *  我特意验证了王道书籍的代码，按照其书的伪代码无法实现？
     *  这份源码中保留有测试源码。
     */
    BinaryTreeNode data;
    /*树不空，栈不空时循环*/
    while((tree != NULL) || (StackIsEmpty(stack) < 0)){
        /*遇到非空二叉树，让左子树进栈*/
        if(tree != NULL){
            StackPush(stack,*tree);
            tree = tree->leftChild;
        }else{/*遇到空二叉树，出栈*/
//            test_wang_dao(stack, tree);
            StackPop(stack,&data);
            printf("%c\n",data.data);
            tree = data.rightChild;
        }
    }
}
int Min(HuffmanTree tree,int k){
    int i = 0;
    int min_weight = 0;
    int min = 0;
    while(tree[i].parent != -1){
        i++;
    }
    min_weight = tree[i].weight;
    min = i;
    for(;i < k; i++){
        if(tree[i].weight < min_weight && tree[i].parent == -1){
            min_weight = tree[i].weight;
            min = i;
        }
    }

    tree[min].parent = 1;
    return min;
}

int selectMin(HuffmanTree tree,int k, int * min1,int * min2){
    *min1 = Min(tree,k);
    *min2 = Min(tree,k);
}

void CreateHufumanTree(HuffmanTree huffman_tree,node_number)
{
    huffman_tree= (HuffmanTree)malloc(node_number * sizeof(HuffmanNode));
    if(huffman_tree == NULL){
        return ;
    }

    for(int i = 0; i < weight_number; i++){
        huffman_tree[i].leftChild = -1;
        huffman_tree[i].rightChild = -1;
        huffman_tree[i].parent = -1;
        huffman_tree[i].weight = *weight;
        weight++;
    }

    for(int i = 0; i < node_number; i++){
        huffman_tree[i].leftChild = -1;
        huffman_tree[i].rightChild = -1;
        huffman_tree[i].parent = -1;
        huffman_tree[i].weight = 0;
    }

    int min1 = 0;
    int min2 = 0;

    for(int i = 0; i < node_number; i++){
        selectMin(huffman_tree,i,&min1,&min2);
        huffman_tree[min1].parent = i;
        huffman_tree[min2].parent = i;
        huffman_tree[min2].leftChild = min1;
        huffman_tree[min2].rightChild = min2;
        huffman_tree[min2].weight = huffman_tree[min1].weight + huffman_tree[min2].weight;
    }
}

void test_Huffman()
{
    int weight_number = 0;
    int * weight = NULL;

    HuffmanTree huffman_tree;
    HuffmanCode huffman_code;

    printf("请输入权值的个数（>1）：");
    scanf("%d",&weight_number);
    weight = (int *)malloc(weight_number * sizeof(int));
    printf("请依次输入%d个权值（整型）：\n", weight_number);

    for(int i = 0; i < weight_number -1; i++){
        scanf("%d",weight + i);
    }
    int node_number = weight_number * 2 - 1;

    CreateHufumanTree(huffman_tree, node_number);

    huffman_code = (HuffmanCode)malloc(weight_number*sizeof(char *));
    if(huffman_code == NULL)
        return ;
    char *code = (char *)malloc(weight_number * sizeof(char));
    if(code == NULL)
        return ;
    code[weight_number - 1] = '\0';
    for(int i = 0; i < weight_number; i++){
        int current = i;
        int father = huffman_tree[i].parent;
        int start = weight_number - 1;
        while (father != -1) {
            if(current == huffman_tree[father].leftChild){
                code[--start] = '0';
            }else {
                code[--start] = '1';
            }
            current = father;
            father = huffman_tree[father].parent;
        }
        huffman_code[i] = (char *) malloc((weight_number- start)*sizeof(char));
        if(huffman_code[i] == NULL)
            return ;
        strcpy(huffman_code[i],code + start);
    }
    free(code);
    code = NULL;

    for(int i = 0;i < weight_number;i++){
        puts(huffman_code[i]);
    }

}

int main(){
    printf("\tUsage: ./main option(1 or 2 ...)\n"
           "\t1 测试二叉树先序、中序、后序遍历的递归实现\n"
           "\t2 测试二叉树层次遍历\n"
           "\t3 测试二叉树先序、中序、后序遍历的非递归实现\n"
//               "4 test noninput create tree\n"
           "\t5 测试Huffman编码\n");

    int option;
    scanf("%d",&option);

    switch(option){
    case 1:
        test_reculsion_traverse();
            break;
    case 2:
        test_level_traverse();
        break;
    case 3:
        test_non_recursion_traverse();
        break;
    case 4:
//        ElemType *data = "IRO##A##CG#W##R##";
//        BinaryTreeLink tree = NULL;
//        CreateBinaryTree2(tree,data);
//        printf("PreOrderTraverse:\n");
//        PreOrderTraverse(tree);
//        printf("data=%c\n",tree->data);
//        printf("data=%c\n",tree->leftChild->data);

        break;
    case 5:
        test_Huffman();
        break;

    default:
        break;
    }

    return 0;
}
